//
// Created by Semir on 2020/5/17.
//

#include <iostream>

using namespace std;

struct RandomListNode {
    int label;
    RandomListNode *next, *random;
    explicit RandomListNode(int x) : label(x), next(nullptr), random(nullptr) {}
};

RandomListNode* Clone(RandomListNode* pHead) {
    if (pHead == nullptr) {
        return nullptr;
    }
    RandomListNode* pNode = pHead;
    RandomListNode* pNext = nullptr;
    RandomListNode* nNode = nullptr;
    //Copy Nodes
    while (pNode) {
        pNext = pNode->next;
        nNode = new RandomListNode(pNode->label);
        nNode->next = pNext;
        pNode->next = nNode;
        pNode = pNext;
    }
    //Copy random link
    pNode = pHead;
    while (pNode) {
        pNext = pNode->next->next;
        if (pNode->random) {
            pNode->next->random = pNode->random->next;
        }
        pNode = pNext;
    }
    //Split
    pNode = pHead;
    RandomListNode* nHead = pNode->next;
    while (pNode) {
        nNode = pNode->next;
        pNext = nNode->next;
        pNode->next = pNext;
        nNode->next = pNext ? pNext->next : nullptr;
        pNode = pNext;
    }
    return nHead;
}

int main() {

    return 0;
}
